package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

import java.util.concurrent.ConcurrentHashMap;

/**
 * @author ：tong nan
 * @date ：Created in 2021/6/3 11:13
 * @description ：完成二叉树counter
 * @modifiedBy ：
 */
public class CompleteBinaryTreeCounter {


    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = leftDepth(root);
        int rightDepth = rightDepth(root);
        if (leftDepth == rightDepth) {
            return (int)(Math.pow(2, leftDepth)) -1;
        }
        return count(root.left) + count(root.right)+1;
    }

    private int leftDepth(TreeNode root) {
        TreeNode temp = root;
        int depth = 0;
        while (temp != null) {
            depth += 1;
            temp = temp.left;
        }
        return depth;
    }

    /**
     * 计算深度, 包含root
     * @param root
     * @return
     */
    private int rightDepth(TreeNode root) {
        TreeNode temp = root;
        int depth = 0;
        while (temp != null) {
            depth +=1;
            temp = temp.right;
        }
        return depth;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.left.left= new TreeNode(7);
        CompleteBinaryTreeCounter counter = new CompleteBinaryTreeCounter();
        System.out.println(counter.count(root));
    }

}
